1. Field of the Invention
The present invention relates to a multiplier, and more particularly, to a high speed digital parallel multiplier, which is, for example, used as a multiplier block in an integer calculating unit (IU) or a floating-point calculating unit (FPU) incorporated into a microprocessor or a digital signal processor (DSP).
2. Description of the Related Art
In general, in order to carry out multiplication of an M-bit operand (multiplicand) and an N-bit operand (multiplier), the multiplicand is multiplied by each bit of the multiplier to generate a partial product. Then, the partial product is shifted in accordance with the bit of the multiplier. Finally, the shifted partial products are added to obtain a final product. For this purpose, multi-input adders are arranged in a two-dimensional plane.
As methods of arrangement of adders, there are two methods: a carry save array (CSA) method and a Wallace tree method.
The CSA method processes bits one by one to supply a carry signal to an adder located at a one-bit higher position. This is similar to a manual calculation method, where the layout thereof corresponds to the logic and is regular, and therefore, the design of layouts is easy. However, in the CSA method, since an execution time depends upon the number of bits of the multiplier, there is some difficulty in achieving high speed operation.
On the other hand, in the Wallace tree method, three bit signals are supplied to a one-bit full adder which is called a three-input Wallace tree circuit (a full adder) "3W", and the output signal (sum signal) is supplied to the next stage full adder of the same bit, and the carry output signal thereof is supplied to the next stage full adder located at a one-bit higher position. In the Wallace tree method, although the speed of operation is high, the circuit layout is not easy since the circuit is irregular.
In a prior art multiplier, the arrangement of adders is a parallelogram which however creates empty or useless areas, thus reducing the integration density of the multiplier. In order to increase the integration density, a multiplier whose arrangement is rectangular has been suggested in Japanese Laid-open Patent Application 55-105732, which will be later explained. In this multiplier, however, the speed of operation is not improved.